CODE 24. Convert Sorted List to Binary Search Tree

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 24 Convert Sorted List to Binary Search Tree/

访问原文「CODE 24. Convert Sorted List to Binary Search Tree」

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

public TreeNode sortedListToBST(ListNode head) {
	// Start typing your Java solution below
	// DO NOT write main() function
	return dfs(head);
}

TreeNode dfs(ListNode head) {
	TreeNode node = null;

	if (head != null) {
		ListNode perMidNode = null;
		ListNode midNode = head;
		ListNode lastNode = head;
		while (null != lastNode.next && null != lastNode.next.next) {
			perMidNode = midNode;
			midNode = midNode.next;
			lastNode = lastNode.next.next;
		}
		if (null != perMidNode) {
			perMidNode.next = null;
		}
		node = new TreeNode(midNode.val);
		TreeNode left = dfs(perMidNode == null ? null : head);
		TreeNode right = dfs(midNode.next);
		node.left = left;
		node.right = right;
	}
	return node;
}